package com.lw.leetcode.sort.b;

import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * 6066. 统计区间中的整数数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/15 21:06
 */
public class CountIntervals {

    public static void main(String[] args) {
        CountIntervals test = new CountIntervals();

//        test.add(8, 43);
//        test.add(13, 16);
//        test.add(26, 33);
//        test.add(28, 36);
//        test.add(29, 37);

        //
        test.add(6, 942);
        test.add(949, 967);
        test.add(988, 996);
        test.add(949, 989);
        int count = test.count();

        System.out.println(count);

    }

    private TreeMap<Integer, Integer> map;
    private int count;

    public CountIntervals() {
        map = new TreeMap<>();
    }

    public void add(int left, int right) {
        int st = left;
        int end = right;
        int c = right - left + 1;
        Integer key = map.floorKey(left);
        if (key != null && key != left) {

            int v = map.get(key);
            if (v + 1 >= left) {
                if (right <= v) {
                    return;
                }
                st = key;
                c -= (v - left + 1);
            }
        }
        while (true) {
            Integer k = map.ceilingKey(left);
            if (k == null) {
                break;
            }
            if (k > right + 1) {
                break;
            }
            Integer v = map.get(k);
            map.remove(k);
            if (v <= right) {
                c -= (v - k + 1);
            } else {
                end = v;
                c -= (right - k + 1);
                break;
            }
        }
        map.put(st, end);
        count += c;
    }

    public int count() {
        return count;
    }

}
